package LC;

import java.util.Stack;

/**
 * https://leetcode.com/problems/longest-valid-parentheses/description/
 * Given a string containing just the characters '(' and ')',
 * find the length of the longest valid (well-formed) parentheses substring.
 * For "(()", the longest valid parentheses substring is "()", which has length = 2.
 * Another example is ")()())", where the longest valid parentheses substring is "()()",
 * which has length = 4.
 */
public class LC_032_LongestValidParentheses_Stack_IfElse_Greedy {
    public static void main(String[] args) {
        String s = ")()()(())(";
        String s1 = "()(()";
        int n = Solution.longestValidParentheses(s);
        System.out.println(n);
    }

    static class Solution {
        static int longestValidParentheses(String s) {
            if (s == null || s.length() == 0)
                return 0;

            int start = -1;
            int maxLength = 0;
            Stack<Integer> stack = new Stack<>();

            for (int i = 0; i < s.length(); i++) {
                if (s.charAt(i) == '(') stack.push(i);
                else {
                    if (!stack.empty()) {
                        stack.pop();
                        if (stack.empty()) maxLength = Math.max(i - start, maxLength);
                        else maxLength = Math.max(i - stack.peek(), maxLength);
                    } else {
                        start = i;
                    }
                }
            }
            return maxLength;
        }
    }
}
